1   /* The Computer Language Shootout
2      http://shootout.alioth.debian.org/
3   
4      contributed by Tony Seebregts
5      modified by 
6   */
7   
8   import java.util.ArrayList;
9   import java.util.Date;
10  import java.util.SortedSet;
11  import java.util.TreeSet;
12  
13  /** First hack at a Java solver for the meteor puzzle - just the IBM 
14    * developerWorks article algorithm optimized with precalculated shapes 
15    * and bitmasks. Should be possible to optimize it some more to take 
16    * advantage of reflections but its turning out to be less obvious 
17    * than expected :-).
18    * <p>
19    * Notes:
20    * <ul>
21    * <li>Seems to run faster without the -server switch.
22    * <li>Testing for islands seems to be slower than just fitting pieces.
23    * </ul>
24    * 
25    * @author Tony Seebregts
26    *
27    */
28    
29  public class meteor
30     { // CONSTANTS
31         
32       private static final int[]    SHIFT = { 0,6,11,17,22,28,33,39,44,50 };
33       private static final long[][] MASK  = { { 0x01L,      0x02L,      0x04L,      0x08L,      0x10L   },
34                       { 0x01L << 6, 0x02L << 6, 0x04L << 6, 0x08L <<  6,0x10L << 6  },
35                       { 0x01L << 11,0x02L << 11,0x04L << 11,0x08L << 11,0x10L << 11 },
36                       { 0x01L << 17,0x02L << 17,0x04L << 17,0x08L << 17,0x10L << 17 },
37                       { 0x01L << 22,0x02L << 22,0x04L << 22,0x08L << 22,0x10L << 22 },
38                       { 0x01L << 28,0x02L << 28,0x04L << 28,0x08L << 28,0x10L << 28 },
39                       { 0x01L << 33,0x02L << 33,0x04L << 33,0x08L << 33,0x10L << 33 },
40                       { 0x01L << 39,0x02L << 39,0x04L << 39,0x08L << 39,0x10L << 39 },
41                       { 0x01L << 44,0x02L << 44,0x04L << 44,0x08L << 44,0x10L << 44 },
42                       { 0x01L << 50,0x02L << 50,0x04L << 50,0x08L << 50,0x10L << 50 }
43                         };
44       
45       private static final boolean DEBUG = false;
46  
47       // CLASS VARIABLES
48       
49       // INSTANCE VARIABLES
50       
51       private SortedSet<String> solutions = new TreeSet<String>();
52       private Entry[]       solution  = new Entry[10];
53       private int       depth     = 0;
54       private Piece[]       pieces    = { new Piece(PIECE0),
55                       new Piece(PIECE1),
56                       new Piece(PIECE2),
57                       new Piece(PIECE3),
58                       new Piece(PIECE4),
59                       new Piece(PIECE5),
60                       new Piece(PIECE6),
61                       new Piece(PIECE7),
62                       new Piece(PIECE8),
63                       new Piece(PIECE9)
64                         };
65         
66       // CLASS METHODS
67  
68       /** Application entry point.
69         * 
70         * @param args  Command line arguments:
71         *      <ul>
72         *      <li> solution limit
73         *      </ul>
74         */
75       
76       public static void main(String[] args)
77          { int N = 2098;
78          
79            // ... parse command line arguments
80          
81            if (args.length > 0)
82           if (args[0].matches("\\d+"))
83              N = Integer.parseInt(args[0]);
84              
85            // ... solve puzzle
86            
87            meteor        puzzle = new meteor ();
88            Date      start;
89            Date      end;
90            long      time;
91            SortedSet<String> solutions;
92            
93            start     = new Date();
94            solutions = puzzle.solve();
95            end   = new Date();
96            time      = end.getTime() - start.getTime();      
97            
98            // ... print result
99              
100           if (solutions.size() > N)
101          System.out.println("ERROR");
102          else if (solutions.size() < N)
103          System.out.println("TIMEOUT");
104          else
105          { if (DEBUG)
106               { System.out.println("START    : " + start);
107             System.out.println("END      : " + end);
108             System.out.println("TIME     : " + time);
109             System.out.println("SOLUTIONS: " + solutions.size ());
110             System.out.println("FIRST    : " + solutions.first());
111             System.out.println("LAST     : " + solutions.last ());
112             System.out.println();
113               }
114            
115            System.out.print(solutions.size () + " solutions found\n\n");
116            print(solutions.first());
117            System.out.print("\n");
118            print(solutions.last ());
119            System.out.print("\n");
120          }
121         }
122 
123      /** Prints out the puzzle.
124        * 
125        * 
126        */
127     
128      private static void print (String solution)
129          { System.out.print(solution.replaceAll("(\\d{5})(\\d{5})","$1 $2")
130                     .replaceAll("(\\d{5})","$1\n")
131                     .replaceAll("(\\d)","$1 "));
132          }
133 
134      // CONSTRUCTORS
135      
136      /** Initialises the puzzle.
137        * 
138        */
139 
140      public meteor ()
141         { for (int i=0; i<10; i++)
142           solution[i] = new Entry();
143         }
144      
145      // INSTANCE METHODS
146      
147      /** Initialises the puzzle and solution set at [0,0]
148        *
149        * @return Sorted list of solution strings.
150        */ 
151      
152      private SortedSet<String> solve()
153          { solve(0x0002004008010020L,0,0);
154          
155            return solutions;
156          }
157      
158      /** Recursively solves the puzzle by fitting pieces into the 
159        * next available hexagon.
160        * 
161        * @param puzzle  Current puzzle bitmask.
162        * @param row     Row of next available hexagon. 
163        * @param col     Column next available hexagon. 
164        * 
165        */
166       
167      private void solve (long puzzle,int row,int col)
168          { for (int ix=0; ix<pieces.length; ix++)
169            { Piece   piece;
170              Shape[] list;
171  
172              // ... find shapes that fit
173              
174              if ((piece = pieces[ix]) == null)
175             continue;
176             else
177             list  = pieces[ix].shapes(row,col);
178                
179              for (Shape shape: list)
180              { // ... fits badly ?
181           
182                if ((shape.bitmap & puzzle) != 0)
183                   continue;
184                
185                // ... try piece in puzzle
186  
187                long clone = puzzle | shape.bitmap;
188  
189                // ... find next position
190                 
191                int irow = row;
192                int icol = col/2 + 1;
193                 
194                next:
195                while (irow < 10)
196                  { while (icol < 5)
197                      { if ((clone & MASK[irow][icol]) == 0)
198                       break next;
199                               
200                        icol++;
201                      }
202                          
203                    irow++;
204                    icol = 0;
205                  }
206                  
207                // ... solve next
208                
209                Entry entry;
210                  
211                pieces[ix]  = null;
212                entry   = solution[depth++];
213                entry.row   = row;
214                entry.col   = col;
215                entry.shape = shape;
216  
217                if (depth == 10)
218                   solutions.add(serialize(solution));
219                   else
220                   solve (clone,irow,2*icol + (irow % 2));
221                 
222                depth--;
223                pieces[ix] = piece;
224              }
225            }
226          }
227       
228      /** Serializes the current solution to a string.
229        * 
230        */
231       
232      private String serialize (Entry[] solution)
233          { char[] puzzle = new char[50];
234            Shape   shape;
235            int     row;
236            int     col;
237            
238            for (Entry entry: solution)
239            { shape = entry.shape;
240              row   = entry.row;
241              col   = entry.col;
242              
243              for (int[] xy: shape.vector)
244              puzzle[5 * (row + xy[0]) + (col + xy[1])/2] = shape.symbol;
245            }
246       
247            return new String(puzzle);
248          }
249     
250      // INNER CLASSES
251      
252      /** Container class for a solution set entry.
253        * 
254        */
255      
256      private static class Entry
257          { public int   row;
258            public int   col;
259            public Shape shape; 
260          }
261      
262      /** Container class for the shapes for a single puzzle piece.
263        * 
264        * 
265        */
266      
267      private static class Piece
268          { private Shape[][][] shapes = new Shape[10][10][];
269          
270            @SuppressWarnings("unchecked")
271            private Piece (Shape[] list)
272                { // ... initialise
273                
274              ArrayList[][] array = new ArrayList[10][10];
275              
276              for (int i=0; i<10; i++)
277                  for (int j=0; j<10; j++)
278                  array[i][j] = new ArrayList<Shape>();
279              
280              // ... generate list
281              
282              for (Shape mutant: list)
283                  for (int row=0; row<=mutant.maxRow; row++)
284                  for (int col=mutant.minCol; col<=mutant.maxCol; col++)
285                      { if (!mutant.islet)
286                       array[row][col].add(new Shape(mutant,row,col));
287                       else if ((row != 0) || (col != 0))
288                       array[row][col].add(new Shape(mutant,row,col));
289                      }
290              
291              for (int row=0; row<10; row++)
292                  for (int col=0; col<10; col++)
293                  shapes[row][col] = (Shape[]) array[row][col].toArray(new Shape[0]);
294                }
295            
296            @SuppressWarnings("unchecked")
297            private Shape[] shapes(int row,int col)
298                { return shapes[row][col];
299                }
300          
301          }
302 
303      /** Container class for the shape vector and bitmap single puzzle piece mutation.
304        * 
305        * 
306        */
307      
308      private static class Shape
309         { private char    symbol;
310           private int[][] vector;
311           private long    bitmap;
312           private int     shift;
313           
314           private boolean islet;
315           private int     maxRow;
316           private int     minCol;
317           private int     maxCol;
318           
319           private Shape (char    symbol,
320                  int[][] vector,
321                  long    bitmap,
322                  int     shift,
323                  boolean islet,
324                  int     maxRow,
325                  int     minCol,
326                  int     maxCol)
327               { this.symbol  = symbol;
328             this.vector  = vector;
329             this.bitmap  = bitmap;
330             this.shift   = shift;
331             
332             this.islet   = islet;
333             this.maxRow  = maxRow;
334             this.minCol  = minCol;
335             this.maxCol  = maxCol;
336               }
337           
338           private Shape (Shape shape,
339                  int   row,
340                  int   col)
341               { this.symbol  = shape.symbol;
342             this.vector  = shape.vector;
343             this.bitmap  = shape.bitmap << ((SHIFT[row] + (col - (row % 2))/2) - shape.shift);
344             
345             this.islet   = shape.islet;
346             this.maxRow  = shape.maxRow;
347             this.minCol  = shape.minCol;
348             this.maxCol  = shape.maxCol;
349               }
350         }
351      
352      // PIECES
353 
354      private static final Shape[] PIECE0 = { new Shape ('0',new int[][] {{3, 5},{2, 4},{1, 3},{0, 2},{0, 0}},0x0000000000082083L,0,false,6,0,4),
355                      new Shape ('0',new int[][] {{4,-2},{3,-1},{2, 0},{1, 1},{0, 0}},0x0000000000421082L,1,false,5,2,8),
356                      new Shape ('0',new int[][] {{1,-7},{1,-5},{1,-3},{1,-1},{0, 0}},0x00000000000003D0L,4,false,8,7,9),
357                      new Shape ('0',new int[][] {{0, 0},{1, 1},{2, 2},{3, 3},{3, 5}},0x00000000000C1041L,0,false,6,0,4),
358                      new Shape ('0',new int[][] {{0, 0},{1,-1},{2,-2},{3,-3},{4,-2}},0x0000000000821084L,2,false,5,3,9),
359                      new Shape ('0',new int[][] {{0, 6},{0, 4},{0, 2},{0, 0},{1,-1}},0x000000000000005EL,1,false,8,1,3),
360                      new Shape ('0',new int[][] {{0, 0},{1, 1},{2, 2},{3, 3},{4, 2}},0x0000000000841041L,0,false,5,0,6),
361                      new Shape ('0',new int[][] {{0, 0},{1,-1},{2,-2},{3,-3},{3,-5}},0x0000000000062108L,3,false,6,5,9),
362                      new Shape ('0',new int[][] {{1, 7},{1, 5},{1, 3},{1, 1},{0, 0}},0x00000000000003C1L,0,false,8,0,2),
363                      new Shape ('0',new int[][] {{4, 2},{3, 1},{2, 0},{1,-1},{0, 0}},0x0000000001041042L,1,false,5,1,7),
364                      new Shape ('0',new int[][] {{3,-3},{2,-2},{1,-1},{0, 0},{0, 2}},0x000000000002108CL,2,false,6,3,7),
365                      new Shape ('0',new int[][] {{0, 0},{0, 2},{0, 4},{0, 6},{1, 7}},0x000000000000020FL,0,false,8,0,2)
366                        };
367 
368      private static final Shape[] PIECE1 = { new Shape ('1',new int[][] {{0, 2},{0, 0},{1,-1},{2, 0},{3,-1}},0x0000000000021046L,1,false,6,1,7),
369                      new Shape ('1',new int[][] {{1, 3},{0, 2},{0, 0},{1,-1},{1,-3}},0x00000000000002CCL,2,false,8,3,6),
370                      new Shape ('1',new int[][] {{3, 3},{2, 4},{1, 3},{1, 1},{0, 0}},0x00000000000420C1L,0,false,6,0,5),
371                      new Shape ('1',new int[][] {{3,-3},{3,-1},{2, 0},{1,-1},{0, 0}},0x0000000000062084L,2,false,6,3,9),
372                      new Shape ('1',new int[][] {{0, 0},{1, 1},{1, 3},{0, 4},{0, 6}},0x00000000000000CDL,0,true, 8,0,3),
373                      new Shape ('1',new int[][] {{0, 0},{1,-1},{2, 0},{2, 2},{3, 3}},0x0000000000083042L,1,false,6,1,6),
374                      new Shape ('1',new int[][] {{0, 6},{1, 5},{1, 3},{0, 2},{0, 0}},0x000000000000018BL,0,true, 8,0,3),
375                      new Shape ('1',new int[][] {{3, 3},{3, 1},{2, 0},{1, 1},{0, 0}},0x0000000000060841L,0,false,6,0,6),
376                      new Shape ('1',new int[][] {{3,-3},{2,-4},{1,-3},{1,-1},{0, 0}},0x00000000000208C4L,2,false,6,4,9),
377                      new Shape ('1',new int[][] {{1,-1},{0, 0},{0, 2},{1, 3},{1, 5}},0x0000000000000346L,1,false,8,1,4),
378                      new Shape ('1',new int[][] {{0, 0},{0, 2},{1, 3},{2, 2},{3, 3}},0x0000000000041083L,0,false,6,0,6),
379                      new Shape ('1',new int[][] {{0, 0},{1, 1},{2, 0},{2,-2},{3,-3}},0x0000000000023104L,2,false,6,3,8)
380                        };
381 
382      private static final Shape[] PIECE2 = { new Shape ('2',new int[][] {{1, 1},{0, 0},{2, 0},{2,-2},{2,-4}},0x0000000000003904L,2,false,7,4,8),
383                      new Shape ('2',new int[][] {{2, 4},{1, 5},{2, 2},{1, 1},{0, 0}},0x0000000000003141L,0,false,7,0,4),
384                      new Shape ('2',new int[][] {{3,-1},{3, 1},{2,-2},{1,-1},{0, 0}},0x0000000000060842L,1,false,6,2,8),
385                      new Shape ('2',new int[][] {{1,-1},{2, 0},{0, 0},{0, 2},{0, 4}},0x000000000000104EL,1,false,7,1,5),
386                      new Shape ('2',new int[][] {{0, 0},{1,-1},{0, 2},{1, 3},{2, 4}},0x0000000000004146L,1,false,7,1,5),
387                      new Shape ('2',new int[][] {{0, 2},{0, 0},{1, 3},{2, 2},{3, 1}},0x0000000000021083L,0,true, 6,0,6),
388                      new Shape ('2',new int[][] {{0, 2},{1, 3},{0, 0},{1,-1},{2,-2}},0x0000000000000946L,1,false,7,2,6),
389                      new Shape ('2',new int[][] {{1, 5},{2, 4},{0, 4},{0, 2},{0, 0}},0x0000000000002107L,0,false,7,0,4),
390                      new Shape ('2',new int[][] {{3, 1},{3,-1},{2, 2},{1, 1},{0, 0}},0x0000000000062082L,1,false,6,1,7),
391                      new Shape ('2',new int[][] {{2,-4},{1,-5},{2,-2},{1,-1},{0, 0}},0x0000000000003148L,3,false,7,5,9),
392                      new Shape ('2',new int[][] {{1,-1},{0, 0},{2, 0},{2, 2},{2, 4}},0x0000000000007042L,1,false,7,1,5),
393                      new Shape ('2',new int[][] {{0, 0},{0, 2},{1,-1},{2, 0},{3, 1}},0x0000000000041046L,1,false,6,1,7)
394                        };
395 
396      private static final Shape[] PIECE3 = { new Shape ('3',new int[][] {{0, 0},{2, 0},{1,-1},{2,-2},{2,-4}},0x0000000000003884L,2,false,7,4,9),
397                      new Shape ('3',new int[][] {{1, 5},{2, 2},{1, 3},{1, 1},{0, 0}},0x00000000000011C1L,0,false,7,0,4),
398                      new Shape ('3',new int[][] {{3, 1},{2,-2},{2, 0},{1,-1},{0, 0}},0x0000000000041842L,1,false,6,2,8),
399                      new Shape ('3',new int[][] {{2, 0},{0, 0},{1, 1},{0, 2},{0, 4}},0x0000000000000847L,0,false,7,0,5),
400                      new Shape ('3',new int[][] {{1,-3},{0, 0},{1,-1},{1, 1},{2, 2}},0x00000000000041C4L,2,false,7,3,7),
401                      new Shape ('3',new int[][] {{0, 0},{1, 3},{1, 1},{2, 2},{3, 1}},0x00000000000210C1L,0,true, 6,0,6),
402                      new Shape ('3',new int[][] {{1, 3},{0, 0},{1, 1},{1,-1},{2,-2}},0x00000000000009C2L,1,false,7,2,6),
403                      new Shape ('3',new int[][] {{2, 4},{0, 4},{1, 3},{0, 2},{0, 0}},0x0000000000002087L,0,false,7,0,5),
404                      new Shape ('3',new int[][] {{3,-1},{2, 2},{2, 0},{1, 1},{0, 0}},0x0000000000023082L,1,false,6,1,7),
405                      new Shape ('3',new int[][] {{1,-5},{2,-2},{1,-3},{1,-1},{0, 0}},0x00000000000021C8L,3,false,7,5,9),
406                      new Shape ('3',new int[][] {{0, 0},{2, 0},{1, 1},{2, 2},{2, 4}},0x0000000000003841L,0,false,7,0,5),
407                      new Shape ('3',new int[][] {{0, 0},{1,-3},{1,-1},{2,-2},{3,-1}},0x00000000000410C4L,2,false,6,3,9)
408                        };
409 
410      private static final Shape[] PIECE4 = { new Shape ('4',new int[][] {{1, 5},{2, 2},{1, 3},{0, 2},{0, 0}},0x0000000000001183L,0,false,7,0,4),
411                      new Shape ('4',new int[][] {{3, 1},{2,-2},{2, 0},{1, 1},{0, 0}},0x0000000000041882L,1,false,6,2,8),
412                      new Shape ('4',new int[][] {{2, 0},{0, 0},{1, 1},{1, 3},{0, 4}},0x00000000000008C5L,0,true, 7,0,5),
413                      new Shape ('4',new int[][] {{1,-3},{0, 0},{1,-1},{2, 0},{2, 2}},0x00000000000060C4L,2,false,7,3,7),
414                      new Shape ('4',new int[][] {{0, 0},{1, 3},{1, 1},{2, 0},{3, 1}},0x00000000000208C1L,0,false,6,0,6),
415                      new Shape ('4',new int[][] {{0, 0},{2, 0},{1,-1},{1,-3},{2,-4}},0x00000000000028C4L,2,false,7,4,9),
416                      new Shape ('4',new int[][] {{0, 0},{1,-3},{1,-1},{2, 0},{3,-1}},0x00000000000420C4L,2,false,6,3,9),
417                      new Shape ('4',new int[][] {{1, 3},{0, 0},{1, 1},{2, 0},{2,-2}},0x0000000000001982L,1,false,7,2,6),
418                      new Shape ('4',new int[][] {{2, 4},{0, 4},{1, 3},{1, 1},{0, 0}},0x00000000000020C5L,0,true, 7,0,5),
419                      new Shape ('4',new int[][] {{3,-1},{2, 2},{2, 0},{1,-1},{0, 0}},0x0000000000023042L,1,false,6,1,7),
420                      new Shape ('4',new int[][] {{1,-3},{2, 0},{1,-1},{0, 0},{0, 2}},0x00000000000020CCL,2,false,7,3,7),
421                      new Shape ('4',new int[][] {{0, 0},{2, 0},{1, 1},{1, 3},{2, 4}},0x00000000000028C1L,0,false,7,0,5)
422                        };
423 
424      private static final Shape[] PIECE5 = { new Shape ('5',new int[][] {{0, 2},{1, 1},{0, 0},{1,-1},{2,-2}},0x00000000000008C6L,1,false,7,2,7),
425                      new Shape ('5',new int[][] {{1, 5},{1, 3},{0, 4},{0, 2},{0, 0}},0x0000000000000187L,0,false,8,0,4),
426                      new Shape ('5',new int[][] {{3, 1},{2, 0},{2, 2},{1, 1},{0, 0}},0x0000000000021841L,0,false,6,0,7),
427                      new Shape ('5',new int[][] {{2,-4},{1,-3},{2,-2},{1,-1},{0, 0}},0x00000000000018C4L,2,false,7,4,9),
428                      new Shape ('5',new int[][] {{0, 0},{0, 2},{1, 1},{1, 3},{1, 5}},0x00000000000001C3L,0,false,8,0,4),
429                      new Shape ('5',new int[][] {{0, 0},{1, 1},{1,-1},{2, 0},{3, 1}},0x00000000000410C2L,1,false,6,1,8),
430                      new Shape ('5',new int[][] {{0, 2},{0, 0},{1, 1},{1,-1},{1,-3}},0x00000000000001CCL,2,false,8,3,7),
431                      new Shape ('5',new int[][] {{2, 4},{1, 3},{2, 2},{1, 1},{0, 0}},0x00000000000030C1L,0,false,7,0,5),
432                      new Shape ('5',new int[][] {{3,-1},{2, 0},{2,-2},{1,-1},{0, 0}},0x0000000000021842L,1,false,6,2,9),
433                      new Shape ('5',new int[][] {{1,-1},{1, 1},{0, 0},{0, 2},{0, 4}},0x00000000000000CEL,1,false,8,1,5),
434                      new Shape ('5',new int[][] {{0, 0},{1, 1},{0, 2},{1, 3},{2, 4}},0x00000000000020C3L,0,false,7,0,5),
435                      new Shape ('5',new int[][] {{0, 0},{1,-1},{1, 1},{2, 0},{3,-1}},0x00000000000210C2L,1,false,6,1,8)
436                        };
437 
438      private static final Shape[] PIECE6 = { new Shape ('6',new int[][] {{1, 1},{0, 0},{1,-1},{1,-3},{2,-4}},0x00000000000009C4L,2,false,7,4,8),
439                      new Shape ('6',new int[][] {{2, 4},{1, 5},{1, 3},{0, 2},{0, 0}},0x0000000000002183L,0,false,7,0,4),
440                      new Shape ('6',new int[][] {{3,-1},{3, 1},{2, 0},{1, 1},{0, 0}},0x0000000000061082L,1,false,6,1,8),
441                      new Shape ('6',new int[][] {{1,-5},{2,-4},{1,-3},{1,-1},{0, 0}},0x00000000000011C8L,3,false,7,5,9),
442                      new Shape ('6',new int[][] {{0, 0},{1,-1},{1, 1},{2, 2},{2, 4}},0x00000000000060C2L,1,false,7,1,5),
443                      new Shape ('6',new int[][] {{0, 2},{0, 0},{1, 1},{2, 0},{3, 1}},0x0000000000020843L,0,false,6,0,7),
444                      new Shape ('6',new int[][] {{0, 0},{1, 1},{1,-1},{2,-2},{2,-4}},0x0000000000001984L,2,false,7,4,8),
445                      new Shape ('6',new int[][] {{1, 5},{2, 4},{1, 3},{1, 1},{0, 0}},0x00000000000021C1L,0,false,7,0,4),
446                      new Shape ('6',new int[][] {{3, 1},{3,-1},{2, 0},{1,-1},{0, 0}},0x0000000000061042L,1,false,6,1,8),
447                      new Shape ('6',new int[][] {{2,-2},{1,-3},{1,-1},{0, 0},{0, 2}},0x00000000000010CCL,2,false,7,3,7),
448                      new Shape ('6',new int[][] {{1,-1},{0, 0},{1, 1},{1, 3},{2, 4}},0x00000000000041C2L,1,false,7,1,5),
449                      new Shape ('6',new int[][] {{0, 0},{0, 2},{1, 1},{2, 2},{3, 1}},0x0000000000021043L,0,false,6,0,7)
450                        };
451 
452      private static final Shape[] PIECE7 = { new Shape ('7',new int[][] {{0, 2},{1, 1},{0, 0},{2, 0},{2,-2}},0x0000000000001886L,1,false,7,2,7),
453                      new Shape ('7',new int[][] {{1, 5},{1, 3},{0, 4},{1, 1},{0, 0}},0x00000000000001C5L,0,true, 8,0,4),
454                      new Shape ('7',new int[][] {{3, 1},{2, 0},{2, 2},{1,-1},{0, 0}},0x0000000000043042L,1,false,6,1,7),
455                      new Shape ('7',new int[][] {{2,-2},{1,-1},{2, 0},{0, 0},{0, 2}},0x0000000000001846L,1,false,7,2,7),
456                      new Shape ('7',new int[][] {{0, 0},{0, 2},{1, 1},{0, 4},{1, 5}},0x0000000000000147L,0,false,8,0,4),
457                      new Shape ('7',new int[][] {{0, 0},{1, 1},{1,-1},{2, 2},{3, 1}},0x00000000000420C2L,1,false,6,1,7),
458                      new Shape ('7',new int[][] {{0, 4},{0, 2},{1, 3},{0, 0},{1,-1}},0x000000000000014EL,1,false,8,1,5),
459                      new Shape ('7',new int[][] {{2, 4},{1, 3},{2, 2},{0, 2},{0, 0}},0x0000000000003083L,0,false,7,0,5),
460                      new Shape ('7',new int[][] {{3,-1},{2, 0},{2,-2},{1, 1},{0, 0}},0x0000000000021882L,1,false,6,2,8),
461                      new Shape ('7',new int[][] {{1,-1},{1, 1},{0, 0},{1, 3},{0, 4}},0x00000000000001CAL,1,false,8,1,5),
462                      new Shape ('7',new int[][] {{0, 0},{1, 1},{0, 2},{2, 2},{2, 4}},0x0000000000003043L,0,false,7,0,5),
463                      new Shape ('7',new int[][] {{0, 0},{1,-1},{1, 1},{2,-2},{3,-1}},0x00000000000208C2L,1,false,6,2,8)
464                        };
465 
466      private static final Shape[] PIECE8 = { new Shape ('8',new int[][] {{4, 2},{3, 1},{2, 0},{1, 1},{0, 0}},0x0000000000820841L,0,false,5,0,7),
467                      new Shape ('8',new int[][] {{3,-5},{2,-4},{1,-3},{1,-1},{0, 0}},0x0000000000021188L,3,false,6,5,9),
468                      new Shape ('8',new int[][] {{0, 0},{0, 2},{0, 4},{1, 5},{1, 7}},0x0000000000000307L,0,false,8,0,2),
469                      new Shape ('8',new int[][] {{0, 0},{1, 1},{2, 2},{3, 1},{4, 2}},0x0000000000821041L,0,true, 5,0,7),
470                      new Shape ('8',new int[][] {{0, 0},{1,-1},{2,-2},{2,-4},{3,-5}},0x0000000000023108L,3,false,6,5,9),
471                      new Shape ('8',new int[][] {{1, 7},{1, 5},{1, 3},{0, 2},{0, 0}},0x0000000000000383L,0,false,8,0,2),
472                      new Shape ('8',new int[][] {{0, 0},{1, 1},{2, 2},{2, 4},{3, 5}},0x0000000000083041L,0,false,6,0,4),
473                      new Shape ('8',new int[][] {{0, 0},{1,-1},{2,-2},{3,-1},{4,-2}},0x0000000000420842L,1,false,5,2,9),
474                      new Shape ('8',new int[][] {{0, 4},{0, 2},{0, 0},{1,-1},{1,-3}},0x00000000000000DCL,2,false,8,3,5),
475                      new Shape ('8',new int[][] {{3, 5},{2, 4},{1, 3},{1, 1},{0, 0}},0x00000000000820C1L,0,false,6,0,4),
476                      new Shape ('8',new int[][] {{4,-2},{3,-1},{2, 0},{1,-1},{0, 0}},0x0000000000421042L,1,false,5,2,9),
477                      new Shape ('8',new int[][] {{1,-5},{1,-3},{1,-1},{0, 0},{0, 2}},0x00000000000001D8L,3,false,8,5,7)
478                        };
479 
480      private static final Shape[] PIECE9 = { new Shape ('9',new int[][] {{3, 3},{2, 2},{1, 1},{0, 0},{0, 2}},0x0000000000041043L,0,false,6,0,6),
481                      new Shape ('9',new int[][] {{3,-3},{2,-2},{1,-1},{0, 0},{1, 1}},0x0000000000021184L,2,false,6,3,8),
482                      new Shape ('9',new int[][] {{0, 0},{0, 2},{0, 4},{0, 6},{1, 5}},0x000000000000010FL,0,false,8,0,3),
483                      new Shape ('9',new int[][] {{0, 0},{1, 1},{2, 2},{3, 3},{3, 1}},0x0000000000061041L,0,true, 6,0,6),
484                      new Shape ('9',new int[][] {{0, 0},{1,-1},{2,-2},{3,-3},{2,-4}},0x0000000000021884L,2,false,6,4,9),
485                      new Shape ('9',new int[][] {{1, 5},{1, 3},{1, 1},{1,-1},{0, 0}},0x00000000000003C2L,1,false,8,1,4),
486                      new Shape ('9',new int[][] {{0, 0},{1, 1},{2, 2},{3, 3},{2, 4}},0x0000000000043041L,0,false,6,0,5),
487                      new Shape ('9',new int[][] {{0, 0},{1,-1},{2,-2},{3,-3},{3,-1}},0x0000000000061084L,2,false,6,3,9),
488                      new Shape ('9',new int[][] {{0, 6},{0, 4},{0, 2},{0, 0},{1, 1}},0x000000000000004FL,0,false,8,0,3),
489                      new Shape ('9',new int[][] {{3, 3},{2, 2},{1, 1},{0, 0},{1,-1}},0x00000000000820C2L,1,false,6,1,6),
490                      new Shape ('9',new int[][] {{3,-1},{2, 0},{1, 1},{0, 2},{0, 0}},0x0000000000021086L,1,false,6,1,7),
491                      new Shape ('9',new int[][] {{1,-5},{1,-3},{1,-1},{1, 1},{0, 0}},0x00000000000003C8L,3,false,8,5,8)
492                        };
493                        
494     }